\documentclass[11pt]{report}

%IMPORTANTE comando \hyphenation{ma-cro-istru-zio-ne nitro-idrossil-amminico} definisce all'algoritmo di latex come spezzare una parola non presente nel suo vocabolario!!

%INCLUSIONE DI PACCHETTI
\usepackage{graphicx}
\usepackage{rotating}
\usepackage{array}
\usepackage{longtable}
\usepackage{multirow}
\usepackage{wrapfig} 
\usepackage{lastpage}
\usepackage{amssymb}
\usepackage{fancyhdr}
\usepackage[english]{babel}
\usepackage{amssymb}
%\usepackage[T1]{fontenc}
%\usepackage[latin9]{inputenc}
\usepackage[colorlinks=true]{hyperref} %per indice con link alle pagine
\usepackage[a4paper,portrait,left=2.5cm,right=2.5cm,bindingoffset=5mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{color}
%\usepackage{xstring}
\hypersetup{colorlinks,citecolor=black,filecolor=black,linkcolor=red,urlcolor=blue}
\setcounter{secnumdepth}{2} % per numerare anche \subsubsection
\setcounter{tocdepth}{2}% per farlo apparire nell'indice
\frenchspacing
\definecolor{LightMagenta}{cmyk}{0.1,0.8,0,0.1}


%HEADER e FOOTER di tutte le pagine tranne quella in cui compare il titolo del capitolo
\pagestyle{fancy}
\fancyhead{}
\headheight = 54pt
\lhead{Computer Science Theory II}
\lfoot{}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
\rhead{\nouppercase{\leftmark}}
\renewcommand{\chaptermark}[1]{\markboth{\thechapter.\ #1}{}}

%HEADER e FOOTER della pagina dove compare il titolo del capitolo
\fancypagestyle{plain}{
%\lhead{\includegraphics[height=50pt]{images/logoUniPd.png}} %IN ALTO A SINISTRA (POTREBBE ANDARE BENE IL LOGO)
\chead{}
\rhead{\bfseries WS2011/12}%\manualeUtenteVer} %IN ALTO A DESTRA
\lfoot{
\begin{tabular}{lc}
Victor A. Arrascue Ayala & Mtr. 3209050\\
Tobias Domhan  & Mtr.  3202957 \\
\end{tabular}
}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
}

\fancypagestyle{romano}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

\fancypagestyle{empty}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

%PAGINA DI PRESETAZIONE DEL DOCUMENTO
\hyphenation{}
\begin{document}


%\begin{center}
%\thispagestyle{empty}
%\huge\textbf{UNIVERSIT\`A degli Studi di PADOVA}\\[2 cm] %GRUPPO DI APPARTENENZA
%\vspace*{0.5in}
%\LARGE\textbf{Titolo del documento}\\[1.0 cm] %TITOLO DEL DOCUMENTO
%\par\rule{10cm}{.5pt} \par
%{\large 12 Ottobre 2009}   %DATA DI CREAZIONE
%\par\rule{10cm}{.10pt} \par
%\vspace*{1.0in}
%\includegraphics[scale=0.30]{images/logoUniPd.png} \\[2cm] %LOGO GRUPPO
%\Large\textbf{Michele Tonon} %AUTORE
%\par\rule{6cm}{.5pt} \par
%\end{center}



% INDEX
%\newpage
%\thispagestyle{romano}
%\pagenumbering{arabic}
%\tableofcontents


%--------------------------------------------- 


%CONTENT


\newpage
\thispagestyle{plain}

\begin{center}
{\Large \textbf{Exercise Sheet 8}}
\end{center}

\noindent{\textbf{Exercise 8.1}}\\\\
(a)
\begin{itemize}
\item L = \{w $\mid$ w has length at least 3 and its 3rd symbol is a 0\}\\
Regular expression: $\Sigma$$\Sigma$0$\Sigma$*
\item L = \{w $\mid$ w starts with 0 and has odd length, or starts with 1 and has even length\}\\
Regular expression:  0($\Sigma$$\Sigma$)* $\cup$ 1$\Sigma$($\Sigma$$\Sigma$)*
\end{itemize}
(b)\\
To obtain a regular expression one method consists in converting the DFA to a GNFA. This is the DFA A represented by a state-machine diagram:
\begin{center}
\includegraphics[width=0.6\textwidth]{exercise8_1-b-DFA.pdf}
\end{center}
The first step consists in converting the DFA using the algorithm in slide 57:
\begin{center}
\includegraphics[width=0.7\textwidth]{exercise8_1-b-GNFA-complete.pdf}
\end{center}
For the sake of clarity we will omit the edges labeled with the empty set:
\begin{center}
\includegraphics[width=0.7\textwidth]{exercise8_1-b-GNFA.pdf}
\end{center}
In order to obtain the regular expression from the GNFA, we have to rip the states.\\
We first rip state q1:
\begin{center}
\includegraphics[width=0.7\textwidth]{exercise8_1-b-GNFA-RipQ1.pdf}
\end{center}
Now, we rip state q2:
\begin{center}
\includegraphics[width=0.7\textwidth]{exercise8_1-b-GNFA-RipQ2.pdf}
\end{center}
Finally, we rip state q0:
\begin{center}
\includegraphics[width=0.7\textwidth]{exercise8_1-b-GNFA-RipQ0.pdf}
\end{center}
The algorithm convert(G) returns the regular expression, the label of the edge from the start state to the accept state:\\
(0$\cup$((11*0)(0$\cup$1)))*11*0.\\\\
\noindent{\textbf{Exercise 8.2}}\\\\
(a)\\
This language is not regular, which can be shown using the pumping lemma. Lets choose the string $s = a^{\lceil \frac{p}{2}\rceil} b^{\lceil \frac{p}{2}\rceil}$, with $p \in \mathbb{N}^+$.This string has at least a length of $p$. Hence we can use the pumping lemma. \\
Now because $|y| > 0$ and $|xy| \le p$, we know that $y$ must contain at least one $b$. It might as well consist of a number of $a$'s followed by a number of $b$'s. Independent of which case is true, as soon as we pump y we get strings that are not part of the language. If y is to consist of a certain number of b's, it might be that we have to pump several times, so that n exceeds m. Otherwise if y is consisting of both a's and b's, only one pumping step is enough, as the resulting string has a's and b's intermixed several times, which is in stark contrast to the language, demanding all a's in the beginning and all b's in the end. We can conclude by contradiction that this language is not regular.
\\
(b)\\
L = \{b$^{2}$a$^{n}$b$^{m}$a$^{3}$, m, n $\geqslant$ 0\}, $\Sigma$ = \{a, b\}\\
This language is regular. A regular expression is: bba*b*aaa.\\\\
(c)\\
This language is not regular, which can be shown by a proof by contradiction using the pumping lemma:\\
Let's consider the string $s = a^{p^2}$. According to the pumping lemma we decompose this string intro three substrings: $s = xyz$. Let the length of y ($|y|$) be $c$. According to the pumping lemma the following holds for the length c:
\begin{equation}
  \label{eq:1}
  0<c\le p
\end{equation}
Now let's pump twice: $s_2=xy^2z$. The length of the new string is bigger then the one of the old string:
\begin{equation}
  \label{eq:2}
  p^2<p^2+c
\end{equation}
Using (\ref{eq:1}) we get:
\begin{equation}
  \label{eq:3}
  p^2 < p^2 +c \le p^2+p < p^2 + 2p + 1 = (p+1)^2
\end{equation}
So in the end we get:
\begin{equation}
  \label{eq:4}
  p^2 < p^2 +c < (p+1)^2
\end{equation}
Hence the length of the new, pumped string can't be a square. By this contradiction we proofed that the languagge is not regular.

\vspace{1cm}
\noindent{\textbf{Exercise 8.3}}\\\\
(a)\\
The language of all palindromes can be described by the following context-free grammar:\\
G = \{\{S\}, $\Sigma$, R, S\} and R = S$\rightarrow$ t$_{i}$St$_{i}$ $\mid$ t$_{i}$ $\mid$ $\varepsilon$, where t$_{i}$$\in$$\Sigma$.
\\
(b)\\Prove by induction that L(G) = L$_{pal}$ holds.\\
In the following proof I assume that G = \{\{S\}, $\Sigma$, R, S\} and R = S$\rightarrow$ t$_{i}$St$_{i}$ $\mid$ t$_{i}$ $\mid$ $\varepsilon$, where t$_{i}$$\in$$\Sigma$.
\begin{itemize}
\item Base Case: S =  t$_{i}$.\\
S $\in$ L(G), the language defined by grammar G  and it is a palindrome because it reads the same from left to right as from right to left.\\
(we could have chosen also $\varepsilon$ as a base case).
\item Inductive Step: We show that if t$_{i}$St$_{i}$ $\in$ L(G) is a palindrome then t$_{i}$t$_{j}$St$_{j}$t$_{i}$ also holds.\\
In t$_{i}$t$_{j}$St$_{j}$t$_{i}$ if we replace t$_{j}$St$_{j}$ with S', we have that:\\
1) S' = t$_{j}$St$_{j}$  $\in$ L(G) is a palindrome (I.H.)\\
2) t$_{i}$S't$_{i}$ also $\in$L(G), because it can be built according to the set of rules R and it is a palindrome because it reads the same from left to right as from right to left.\\
(q.e.d.)
\end{itemize}



\end{document}

